

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>


<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<base target="_top">
<style type="text/css">
  

/* default css */

table {
  font-size: 1em;
  line-height: inherit;
  border-collapse: collapse;
}


tr {
  
  text-align: left;
  
}


div, address, ol, ul, li, option, select {
  margin-top: 0px;
  margin-bottom: 0px;
}

p {
  margin: 0px;
}


pre {
  font-family: Courier New;
  white-space: pre-wrap;
  margin:0;
}

body {
  margin: 6px;
  padding: 0px;
  font-family: Verdana, sans-serif;
  font-size: 10pt;
  background-color: #ffffff;
  color: #000;
}


img {
  -moz-force-broken-image-icon: 1;
}

@media screen {
  html.pageview {
    background-color: #f3f3f3 !important;
    overflow-x: hidden;
    overflow-y: scroll;
  }

  

  body {
    min-height: 1100px;
    
    counter-reset: __goog_page__;
  }
  
  * html body {
    height: 1100px;
  }
  /* Prevent repaint errors when scrolling in Safari. This "Star-7" css hack
     targets Safari 3.1, but not WebKit nightlies and presumably Safari 4.
     That's OK because this bug is fixed in WebKit nightlies/Safari 4 :-). */
  html*#wys_frame::before {
    content: '\A0';
    position: fixed;
    overflow: hidden;
    width: 0;
    height: 0;
    top: 0;
    left: 0;
  }
  
  .pageview body {
    border-top: 1px solid #ccc;
    border-left: 1px solid #ccc;
    border-right: 2px solid #bbb;
    border-bottom: 2px solid #bbb;
    width: 648px !important;
    margin: 15px auto 25px;
    padding: 40px 50px;
  }
  /* IE6 */
  * html {
    overflow-y: scroll;
  }
  * html.pageview body {
    overflow-x: auto;
  }
  

  
    
    .writely-callout-data {
      display: none;
    }
    

    .writely-footnote-marker {
      background-image: url('MISSING');
      background-color: transparent;
      background-repeat: no-repeat;
      width: 7px;
      overflow: hidden;
      height: 16px;
      vertical-align: top;

      
      -moz-user-select: none;
    }
    .editor .writely-footnote-marker {
      cursor: move;
    }
    .writely-footnote-marker-highlight {
      background-position: -15px 0;
      -moz-user-select: text;
    }
    .writely-footnote-hide-selection ::-moz-selection, .writely-footnote-hide-selection::-moz-selection {
      background: transparent;
    }
    .writely-footnote-hide-selection ::selection, .writely-footnote-hide-selection::selection {
      background: transparent;
    }
    .writely-footnote-hide-selection {
      cursor: move;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }

  


  
  .br_fix span+br:not(:-moz-last-node) {
    
    position:relative;
    
    left: -1ex
    
  }

  
  #cb-p-tgt {
    font-size: 8pt;
    padding: .4em;
    background-color: #ddd;
    color: #333;
  }
  #cb-p-tgt-can {
    text-decoration: underline;
    color: #36c;
    font-weight: bold;
    margin-left: 2em;
  }
  #cb-p-tgt .spin {
    width: 16px;
    height: 16px;
    background: url(//ssl.gstatic.com/docs/clipboard/spin_16o.gif) no-repeat;
  }
}

h6 { font-size: 8pt }
h5 { font-size: 8pt }
h4 { font-size: 10pt }
h3 { font-size: 12pt }
h2 { font-size: 14pt }
h1 { font-size: 18pt }

blockquote {padding: 10px; border: 1px #DDD dashed }

.webkit-indent-blockquote { border: none; }

a img {border: 0}

.pb {
  border-width: 0;
  page-break-after: always;
  /* We don't want this to be resizeable, so enforce a width and height
     using !important */
  height: 1px !important;
  width: 100% !important;
}

.editor .pb {
  border-top: 1px dashed #C0C0C0;
  border-bottom: 1px dashed #C0C0C0;
}

div.google_header, div.google_footer {
  position: relative;
  margin-top: 1em;
  margin-bottom: 1em;
}


/* Table of contents */
.editor div.writely-toc {
  background-color: #f3f3f3;
  border: 1px solid #ccc;
}
.writely-toc > ol {
  padding-left: 3em;
  font-weight: bold;
}
ol.writely-toc-subheading {
  padding-left: 1em;
  font-weight: normal;
}
/* IE6 only */
* html writely-toc ol {
  list-style-position: inside;
}
.writely-toc-none {
  list-style-type: none;
}
.writely-toc-decimal {
  list-style-type: decimal;
}
.writely-toc-upper-alpha {
  list-style-type: upper-alpha;
}
.writely-toc-lower-alpha {
  list-style-type: lower-alpha;
}
.writely-toc-upper-roman {
  list-style-type: upper-roman;
}
.writely-toc-lower-roman {
  list-style-type: lower-roman;
}
.writely-toc-disc {
  list-style-type: disc;
}

/* Ordered lists converted to numbered lists can preserve ordered types, and
   vice versa. This is confusing, so disallow it */
ul[type="i"], ul[type="I"], ul[type="1"], ul[type="a"], ul[type="A"] {
  list-style-type: disc;
}

ol[type="disc"], ol[type="circle"], ol[type="square"] {
  list-style-type: decimal;
}

/* end default css */


  /* default print css */
  @media print {
    body {
      padding: 0;
      margin: 0;
    }

    div.google_header, div.google_footer {
      display: block;
      min-height: 0;
      border: none;
    }

    div.google_header {
      flow: static(header);
    }

    /* used to insert page numbers */
    div.google_header::before, div.google_footer::before {
      position: absolute;
      top: 0;
    }

    div.google_footer {
      flow: static(footer);
    }

    /* always consider this element at the start of the doc */
    div#google_footer {
      flow: static(footer, start);
    }

    span.google_pagenumber {
      content: counter(page);
    }

    span.google_pagecount {
      content: counter(pages);
    }

    .endnotes {
      page: endnote;
    }

    /* MLA specifies that endnotes title should be 1" margin from the top of the page. */
    @page endnote {
      margin-top: 1in;
    }

    callout.google_footnote {
      
      display: prince-footnote;
      footnote-style-position: inside;
      /* These styles keep the footnote from taking on the style of the text
         surrounding the footnote marker. They can be overridden in the
         document CSS. */
      color: #000;
      font-family: Verdana;
      font-size: 10.0pt;
      font-weight: normal;
    }

    /* Table of contents */
    #WritelyTableOfContents a::after {
      content: leader('.') target-counter(attr(href), page);
    }

    #WritelyTableOfContents a {
      text-decoration: none;
      color: black;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }
  }

  @page {
    @top {
      content: flow(header);
    }
    @bottom {
      content: flow(footer);
    }
    @footnotes {
      border-top: solid black thin;
      padding-top: 8pt;
    }
  }
  /* end default print css */


/* custom css */


/* end custom css */

/* ui edited css */

body {
  font-family: Verdana;
  
  font-size: 10.0pt;
  line-height: normal;
  background-color: #ffffff;
}
/* end ui edited css */


/* editor CSS */
.editor a:visited {color: #551A8B}
.editor table.zeroBorder {border: 1px dotted gray}
.editor table.zeroBorder td {border: 1px dotted gray}
.editor table.zeroBorder th {border: 1px dotted gray}


.editor div.google_header, .editor div.google_footer {
  border: 2px #DDDDDD dashed;
  position: static;
  width: 100%;
  min-height: 2em;
}

.editor .misspell {background-color: yellow}

.editor .writely-comment {
  font-size: 9pt;
  line-height: 1.4;
  padding: 1px;
  border: 1px dashed #C0C0C0
}


/* end editor CSS */

</style>

  
  <title>W6 Synchronizacja zegarów</title>

</head>

<body 
    
    >
    
    
    
<div id=mocx style=TEXT-ALIGN:left>
  <b style=COLOR:#3d85c6><font size=5>Synchronizacja zegarów i rozproszone transakcje</font></b><br>
  <hr size=2>
</div>
<br>
Wykład ten poświęcony będzie zagadnieniom synchronizacji w systemach rozproszonych. Ponieważ rozproszony system operacyjny może składać się z pewnej liczby mniej lub bardziej niezależnych komponentów, istotny staje się problem organizacji ich współpracy, synchronizacji.<br>
<br>
<p>
  Sytuacji, w których mamy do czynienia jest bardzo dużo. Np.: dostęp do wspólnych zasobów dzielonych między kilka procesów, ustalanie globalnego czasu itp.<br>
</p>
<p>
  <br>
</p>
<p>
  W pierwszej kolejności zostanie omówiona problematyka synchronizacji zegarów fizycznych oraz logicznych. Zaprezentujemy kilka podstawowych algorytmów służących do synchronizacji zegarów. Zostaną również zaprezentowane niektóre pojęcia niezbędne przy analizie problemów związanych z synchronizacją m.in. pojęcie relacji poprzedzania, diagramy przestrzenno czasowe. Przedstawimy różne podejścia stosowane do konstrukcji zegarów logicznych.<br>
</p>
<p>
  <br>
</p>
<p>
  Po omówieniu synchronizacji zegarów zajmiemy się transakcjami rozproszonymi. We wstępie omówimy model transakcji i przejdziemy do właściwości <i>ACID</i> , które w pewien sposób charakteryzują transakcje. W dalszej kolejności przeanalizujemy różne typy transakcji: płaskie, zagnieżdżone oraz rozproszone. Krótko opiszemy również podejścia do rzeczywistej realizacji transakcji. Po tym przedstawimy zagadnienie sterowania współbieżnością transakcji, a w tym m.in. kwestia szeregowalności, blokowanie dwufazowe oraz pesymistyczne i optymistyczne porządkowanie według znaczników czasowych.
</p>
<br>
<br>
<b style=COLOR:#3d85c6><font size=3>Zegary fizyczne</font></b><br>
<hr size=2><br>
<div id=yeh0 style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2397fmm77rc8_b.png" style=HEIGHT:344px;WIDTH:500px><br>
  <br>
  Układ odmierzający czas jest standardowym wyposażeniem większości dzisiejszych komputerów. Od jego prawidłowego działania zależy często bardzo wiele innych elementów całego systemu komputerowego. Z zegarem związane są zazwyczaj dwa rejestry: <b>rejestr</b> <b>licznika</b> (ang. <i>counter</i> ) oraz <b>rejestr</b> <b>podtrzymujący</b> (ang. <i>holding</i> <i>register</i> ). Wraz z wybijaniem taktów przez czasomierz systemowy zmniejszana jest wartość rejestru licznika. W momencie kiedy jego wartość dojdzie do zera wywoływane jest przerwanie i ładowana jest do niego wartość rejestru podtrzymującego. Zauważmy, że zmieniając wartość rejestru podtrzymującego możemy sterować częstotliwością wywoływania przerwań, a tym samym częstotliwością tzw. <b>impulsów</b> <b>zegara</b> (ang <i>clock</i> <i>tick</i> ).
  <p>
    <br>
  </p>
  <p>
    Dopóki zegar jest używany lokalnie na jednej maszynie kwestia jego niedokładności nie jest aż taka istotna. Procesy korzystają w tym wypadku z jednego zegara, a więc w ramach danej maszyny jego wskazania będą spójne. Problem pojawia się gdy dostępnych mamy kilka maszyn, z których każda posiada swój własny zegar. Ponieważ fizyczne zegary nie są idealne i ich częstotliwości będą się w jakimś stopniu różniły, po pewnym czasie zaczną wskazywać różne wartości. Innymi słowy pojawią się tzw. <b>odchylenia</b> <b>wskazań</b> <b>zegara</b> (ang. <i>clock</i> <i>skew</i> ). W takim przypadku założenie, że zegary fizyczne w danym momencie wskazują identyczny czas jest obarczone pewnym błędem.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Do pomiaru upływu rzeczywistego czasu stosowano wiele różnych metod. Jednym z bardziej przełomowych momentów w tej dziedzinie było wynalezienie zegara atomowego. Wtedy też na nowo zdefiniowano pojęcie sekundy jako liczbę przejść w atomie cezu 133. Przy użyciu takich zegarów liczony jest <b>międzynarodowy</b> <b>czas</b> <b>atomowy</b> (ang<i>.</i> <i>International</i> <i>Atomic</i> <i>Time</i> <i>–</i> <i>TAI</i> ), który ustanawiany jest poprzez uśrednienie pomiarów z różnych laboratoriów. Okazało się, że mimo swoich zalet podejście to nie jest pozbawione błędu. Ponieważ średni dzień słoneczny trwa coraz dłużej pojawia się rozbieżność z międzynarodowym czasem atomowym. W celu rozwiązania tego problemu wprowadzono sekundy przestępne. System pomiaru czasu, który uwzględnia to ulepszenie nazywamy <b>uniwersalnym</b> <b>czasem</b> <b>koordynowanym</b> (ang. <i>Universal</i> <i>Coordinated</i> <i>Time</i> <i>–</i> <i>UTC</i> ). <i>UTC</i> jest podstawą dzisiejszego pomiaru czasu wśród cywilnych zastosowań. Wskazania <i>UTC</i> udostępniono również osobom, które chcą znać dokładny czas. W tym celu Narodowy Instytut Czasu Standardowego (ang. <i>National</i> <i>Institute</i> <i>of</i> <i>Standard</i> <i>Time</i> <i>–</i> <i>NIST</i> ) posiada nadajnik radiowy o literach wywoławczych WWV, który co sekundę wysyła impuls.
  </p>
  <br>
  <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd1 title=Sr-6-wyk-2.0-Slajd1> </a><br>
  <b style=COLOR:#3d85c6><font size=3>Algorytmy synchronizacji zegarów</font></b><br>
  <hr size=2><br>
  <div id=k8j: style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2398fg5cd9fw_b.png" style=HEIGHT:344px;WIDTH:500px><br>
    <br>
    W przypadku synchronizacji zegarów możemy wyróżnić różne cele. Jednym z nich może być potrzeba zsynchronizowania grupy maszyn z jedną dedykowaną stacją, która ma np. odbiornik WWV. Potrzeba synchronizacji może zaistnieć również, gdy nie ma wyróżnionej pewnej stacji pomiarowej, ale musimy skoordynować działanie grupy maszyn.<br>
    <br>
    <p>
      Do rozwiązania tych problemów istnieje wiele algorytmów, z których część zaprezentujemy w dalszej części wykładu. W tym momencie omówimy pewien wspólny dla tych algorytmów model systemu związanego z pomiarem czasu. W modelu tym zakładamy istnienie pewnego idealnego zegara. Oznaczmy dla wygody jego wartość jako <i>t</i> . Każda maszyna, która posiada czasomierz wyznacza czas o wartości <i>C</i> . Jeżeli maszyna <i>p</i> ma za zadanie wyznaczać czas <i>t</i> , wartość jej czasu oznaczamy jako <i>Cp(t</i> <i>).</i> W tym momencie może wystąpić kilka przypadków. W wypadku kiedy <i>Cp(t</i> <i>)</i> <i>=</i> <i>t</i> mamy do czynienia z sytuacją, w której zegar w maszynie jest zegarem doskonałym (<i>dC/dt</i> <i>=</i> <i>1</i> ). W praktyce występuje jednak sytuacja, w której zegary są szybsze lub wolniejsze w stosunku do zegara doskonałego <i>t</i> (<i>dC/dt</i> różne od 1). Takie zegary powinny być poddawane okresowej resynchronizacji.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Algorytm Cristiana</font></b><br>
    <hr size=2><br>
  </div>
  <div id=rdqv style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2399d5p52tcd_b.png" style=HEIGHT:344px;WIDTH:500px><br>
    <br>
    Algorytm ten jest przeznaczenie głównie dla środowisk rozproszonych w których jeden z węzłów jest <b>serwerm</b> <b>czasu</b> (ang. <i>time</i> <i>server</i> ) (np. posiada odbiornik WWV). W algorytmie tym zakłada się, że każda maszyna co pewien określony czas (wartość tego czasu zależy m.in. od maksymalnego odchylenia zegarów jakie będziemy tolerować) wysyła do serwera czasu zapytanie o podanie aktualnego czasu. Po otrzymaniu tego zapytania, serwer odpowiada prędko jak tylko może i przesyła aktualny czas <i>UTC</i> . Nadawca z kolei, po otrzymaniu informacji o czasie od serwera, zanim ustawi wartość swojego zegara, musi uwzględnić parę kwestii. Mianowicie, zwykłe przepisanie czasu nadesłanego z serwera mogłoby spowodować, że czas płynie wstecz. Może się tak zdarzyć jeżeli zegar nadawcy wymierza czas zbyt szybko. Opcja prostego przepisania czasu więc odpada. Poza tym istnieje pewien koszt w postaci czasu komunikacji. Taki koszt powoduje oczywiście, że wartość czasu <i>UTC</i> wysłana przez serwer jest nieaktualna po nadejściu do nadawcy zapytania. Aby rozwiązać ten problem nadawca może np. zapamiętać przedział czasowy zawarty pomiędzy momentem <i>T0</i> , w którym wysłano zapytanie do serwera i momentem <i>T1</i> , kiedy przyszła odpowiedź z serwera. W najprostszym przypadku przyjmuje się, że połowa tego przedziału jest czasem komunikacji od serwera do klienta <i>((</i> <i>T1</i> <i>–</i> <i>T0</i> <i>)</i> <i>/</i> <i>2</i> ). Jeśli dodatkowo znamy czas (<i>T2</i> ) przetwarzania zapytania przez serwer, możemy poprawić oszacowanie czasu przez nadawcę i jako czas przesyłania komunikatu bierzemy wtedy połowę wartości <i>(</i> <i>T1</i> <i>-</i> <i>T0</i> <i>-</i> <i>T2).<br>
    <br>
    </i>
    <p>
      W przypadku, gdy wiemy, że czas przesyłania komunikatu może się różnić przy każdym przesłaniu wiadomości z i do serwera, zaproponowano wykonywanie kilku pomiarów i odpowiednie ich uśrednianie.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Ilustracja algorytmu Cristiana</font></b><br>
    <hr size=2><br>
  </div>
  <div id=id7f style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2400w8k9p8c2_b.png" style=HEIGHT:343px;WIDTH:500px><br>
    <br>
    W przykładzie zaprezentowanym na powyższej ilustracji pewna maszyna chce zsynchronizować swój lokalny zegar z zegarem serwera czasu. W tym celu wysyła komunikat z pytaniem o czas do serwera czasu. Ten gdy tylko może, odsyła do maszyny wiadomość zawierającą jego lokalny czas oraz ew. czas przetwarzania zapytania. Po otrzymaniu danych o czasie, maszyna oblicza nowy czas i ustawia odpowiednio swój zegar.<br>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Algorytm z Berkeley</font></b><br>
    <hr size=2><br>
    <div id=k18j style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2401ctwn8cgk_b.png" style=HEIGHT:343px;WIDTH:500px><br>
      <br>
      W przeciwieństwie do algorytmu Cristiana w przypadku algorytmu z Berkeley serwer czasu jest aktywny i co pewien okres czasu wypytuje każdą maszynę o jej aktualny czas. Po zebraniu odpowiedzi od grupy maszyn serwer uśrednia ich czasy. Na podstawie takiej wyliczonej wartości czasu, serwer każe odpowiednim maszynom ustawić nową wartość czasu lub zwolnić działanie do chwili kiedy osiągną odpowiednią wartość.<br>
      <br>
      <p>
        Takie podejście do synchronizacji zegarów fizycznych może być użyte m.in. w systemie, w którym nie ma specjalnych serwerów czasu, a jedynie chodzi o wspólne ustalenie jednej podstawy czasu.
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Algorytm uśrednienia</font></b><br>
      <hr size=2><br>
      <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd5 title=Sr-6-wyk-2.0-Slajd5> </a>
      <div id=yzye style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2402hppk77f2_b.png" style=HEIGHT:343px;WIDTH:500px><br>
        <br>
        <p>
          Algorytm uśredniania jest algorytmem zdecentralizowanym. W podejściu tym czas dzieli się na przedziały o określonym i stałym rozmiarze. Na początku każdego przedziału następuje resynchronizacja wszystkich zegarów. Polega to na tym, że każda maszyna rozgłasza wtedy aktualny czas swojego zegara. W momencie wysłania maszyna uruchamia lokalny czasomierz i rozpoczyna zbieranie komunikatów od innych maszyn. Komunikaty rozgłoszeniowe mogą przychodzić w różnych chwilach od różnych nadawców. Gdy zostaną zebrane wszystkie odpowiedzi obliczana jest na ich podstawia nowa wartość czasu. W najprostszym przypadku wykorzystuje się uśrednianie. W zmodyfikowanej wersji odrzuca się dodatkowo przed uśrednianiem skrajne wartości, aby nie zaburzały zbytnio wyniku. W jeszcze bardziej rozbudowanej wersji są brane pod uwagę m.in. czasy przesyłania komunikatów.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Algorytm Marzullo</font></b><br>
        <hr size=2><br>
        <div id=zete style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2403dt4jhgf5_b.png" style=HEIGHT:341px;WIDTH:500px>
        </div>
        <br>
      </div>
    </div>
    Algorytm Marzullo jest używany do oszacowania czasu na podstawie informacji z pewnej liczby zaszumianych źródeł czasu tzn. źródeł których czas jest podany w postaci przedziałów. Zmodyfikowana wersja tego algorytmu, który zostanie zaprezentowany w dalszej części wykładu, jest wykorzystywany w popularnym <b>sieciowym</b> <b>protokole</b> <b>czasu</b> (ang. <i>Network</i> <i>Time</i> <i>Protocol</i> <i>–</i> <i>NTP</i>).<br>
    <br>
    <p>
      Ogólna koncepcja algorytmu polega na znalezieniu najmniejszego przedziału czasu spójnego z jak największą liczbą źródeł czasu. Poprzez pojęcie spójnych przedziałów rozumieć tu należy przedziały, które na siebie zachodzą, czyli mają pewna część wspólną.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Po odnalezieniu szukanego przedziału czasowego do wyznaczenia konkretnej wartości czasu mogą być wykorzystane różne metody. Najprostsza z nich bierze po prostu środek przedziału. Bardziej wyrafinowane metody wykorzystują metody probabilistyczne do wyznaczenia czasu.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Jak już wspomniano w algorytmie używa się przedziałów do opisania czasu mierzonego przez zegary z różnych źródeł. Każdy przedział w postaci [t-d, t+d] w algorytmie reprezentowany jest przez dwie pary w formie &lt;znacznik czasowy, typ&gt;: &lt;t-d; -1&gt; oraz &lt;t+d; +1&gt;. Wartość -1 oznacza tutaj parę zawierającą wartość początku przedziału, natomiast +1 oznacza jego koniec.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      W momencie kiedy dana maszyna otrzyma informacje o czasie na innych maszynach, algorytm może rozpocząć swoje działanie. W pierwszej kolejności pary, które reprezentują końce przedziałów czasowych są sortowane na liście według ich znaczników czasowych. Jeżeli pewne pary mają ten sam znacznik czasowy, jednym z rozwiązań jest umieszczenie par z typem +1 przed parami z typem -1 (robi się tak w celu uniknięcia problemu z przedziałami nakładającymi się tylko swoimi końcami). Po posortowaniu listy, brane są kolejne pary i sprawdzane w wyniku porównania z dotychczasowym najlepszym rozwiązaniem. Porównanie polega na sprawdzeniu czy oba przedziały się nakładają. Jeżeli tak, to wartość ich części wspólnej staje się ewentualnie nowym najlepszym rozwiązaniem (zależy to od tego czy wcześniej nie został już znaleziony przedział, który zawiera się w większej liczbie innych przedziałów).<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Na slajdzie przedstawiono szczegóły algorytmu, a tutaj opiszemy znaczenie poszczególnych zmiennych użytych w algorytmie: <i>best</i> – największa dotychczasowa liczba nakładających się przedziałów; <i>current</i> – bieżąca liczba nakładających się przedziałów; <i>[</i> <i>beststart</i> <i>,</i> <i>bestend</i> <i>]</i> – najlepszy znaleziony do tej pory przedział; <i>i</i> – pewien indeks; <i>offset[i</i> <i>]</i> – znacznik czasowy pary o indeksie <i>i</i>&nbsp;; <i>type[i</i> <i>]</i> – typ pary o indeksie <i>i</i> .
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Algorytm Marzullo - przykład</font></b><br>
    <hr size=2><br>
  </div>
  <div id=w4hz style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2404dswfhpcp_b.png" style=HEIGHT:343px;WIDTH:500px><br>
    <br>
    Aby zaprezentować przykład wykonania algorytmu Marzullo załóżmy, że mamy podane pewne przedziały czasowe, zaprezentowane na slajdzie jako dane wejściowe. Po zebraniu takich przedziałów, maszyna przystępuje do obliczania nowego czasu. W pierwszej kolejności, zgodnie z algorytmem, wyliczane są odpowiednie pary dla każdego przedziału (na slajdzie sekcja: <i>Tworzenie</i> <i>par</i> ). Pary te są następnie sortowane według algorytmu podanego wcześniej.<br>
    <br>
    <br>
    <div id=i28l style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2405g58fkncs_b.png" style=HEIGHT:342px;WIDTH:500px><br>
      <br>
      Zgodnie z posortowaną wcześniej listą par, bierzemy kolejne pary i obliczamy przedział wynikowy. Kolejne etapy wykonywania algorytmu przedstawione zostały na slajdzie. Wyliczonym przedziałem jest w tym przypadku [4, 6].<br>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Algorytm przycięcia</font></b><br>
      <hr size=2><br>
      <div id=t54g style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2406p3xhhmcb_b.png" style=HEIGHT:343px;WIDTH:500px><br>
        <br>
        Algorytm przecięcia (ang. <i>intersection</i> <i>algorithm</i> ) jest zmodyfikowaną wersją algorytmu Marzullo. Celem tego algorytmu jest znalezienie największego pojedynczego przecięcia przedziałów, które będzie zawierało czas mierzony przez zegary o określonej dokładności (ang. <i>truechimer</i> ). Podobnie jak w przypadku algorytmu Marzullo, mamy danych <i>m</i> przedziałów w postaci <i>[</i> <i>t-d</i> <i>,</i> <i>t+d</i> <i>].<br>
        <br>
        </i>
        <p>
          Główna różnica pomiędzy algorytmem Marzullo, a jego modyfikacją jest fakt, iż wynik uzyskiwany w przypadku tego pierwszego niekoniecznie zawiera środek sumy wszystkich przedziałów. W wypadku algorytmu przecięcia przedział wynikowy zawiera: przedział, który daje w wyniku algorytm Marzullo, a poza tym wspomniany wcześniej środek sumy przedziałów. Taki przedział jest większy, od tego uzyskanego poprzednią wersją algorytmu. To z kolei pozwala na zastosowanie pewnych danych statystycznych w celu wybrania punktu wynikowego z tego przedziału.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Algorytm szuka przedziału, który pokrywałby się z przedziałami <i>m-f</i> źródeł czasu, gdzie <i>f</i> jest liczbą źródeł z wartością czasu poza przedziałem ufności (błędne źródła). Aby otrzymać najlepszy wynik, zakłada się, że <i>f</i> powinno być tak małe jak to tylko możliwe, a wynik jest sensowny gdy <i>f</i> <i>&lt;</i> <i>m/2</i> (liczba błędnych źródeł nie powinna stanowić więcej niż połowę liczby wszystkich źródeł).
        </p>
        <p>
          W porównaniu z algorytmem Marzullo w przypadku tego algorytmu każdy przedział jest reprezentowany przez trzy pary: początek przedziału &lt;t-d; -1&gt;, środek przedziału &lt;t; 0&gt; oraz koniec przedziału &lt;t+d; +1&gt;.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Oprócz wcześniej wspomnianych struktur danych, algorytm używa zmiennych: <i>endcount</i> – bieżąca liczba końców przedziałów, <i>midcount</i> – bieżąca liczba środków przedziałów, <i>low</i> – wartość dolnego końca przedziału wynikowego, <i>high</i> – wartość górnego końca przedziału.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Jak wspomniano działanie algorytmu polega na próbie znalezienia przedziału spójnego z <i>m-f</i> źródłami czasu. Przed rozpoczęciem głównej części algorytmu jest tworzona posortowana lista wszystkich dostępnych par, które reprezentują dostępne przedziały czasowe. Sortowanie odbywa się analogicznie jak w algorytmie Murzallo. Algorytm wykonuję się w pętli z rosnącą wartością <i>f</i> . Na początku zakłada się, że nie ma błędnych źródeł czasu, czyli <i>f</i> <i>=</i> <i>0</i> . Pętla wykonuje się do momentu kiedy zostanie znaleziony zadowalający przedział lub wartość <i>f</i> będzie równa bądź większa od <i>m/2</i> . Wewnątrz głównej pętli wykonywane są dwie mniejsze pętle, z których jedna szuka dolnego końca przedziału wynikowego, a druga górnego końca przedziału wynikowego. W skrócie można napisać, iż jedna pętla przegląda na liście pary &lt;znacznik czasowy, typ&gt; w kolejności rosnącej, a druga pętla robi to w kolejności malejącej. Każda z pętli kończy się w momencie, gdy liczba rozpatrzonych przez nie przedziałów mających wspólną część będzie równa lub większa od wartość <i>m-f</i> . Pod koniec obu pętli sprawdzane jest czy liczba środków przedziałów znajdujących się poza przedziałem wynikowym nie przekracza liczby <i>f</i> błędnych źródeł czasu. Jeżeli nie przekracza główna pętla jest kończona i otrzymujemy odpowiedni wynik.
        </p>
        <br>
        <br>
      </div>
      <div id=qtlp style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2407ckx3hddw_b.png" style=HEIGHT:342px;WIDTH:500px><br>
        <br>
        Dalsza część algorytmu przedstawionego na poprzednim slajdzie.<br>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Algorytm przycięcia - przykład</font></b><br>
        <hr size=2><br>
        <div id=mf7y style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2408fkr5jhf5_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Podobnie jak w przypadku oryginalnego algorytmu Marzullo, dana jest lista przedziałów na podstawie, których powstaje posortowana odpowiednio lista par. W przypadku tego algorytmu dla każdego przedziału wejściowego są konstruowane 3 pary, a nie 2 jak to miało miejsce w poprzednim algorytmie. Analizując w kilku krokach (ze zmieniającym się wartością <i>f</i> ) daną listę par od początku i od końca, otrzymujemy przedział wynikowy [4, 10].<br>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Relacja uprzedniości zdarzeń</font></b><br>
          <hr size=2><br>
          <div id=c821 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2409gtjmrqv8_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Analizując zagadnienie synchronizacji należy wspomnieć o <b>relacji</b> <b>uprzedniości</b> <b>zdarzeń</b> (ang. <i>happened</i> <i>before</i> <i>relation</i> ) często omawianej w kontekście systemów rozproszonych.<br>
            <br>
            <p>
              Relacja ta określa, kiedy pewne zdarzenie <i>a</i> poprzedza inne zdarzenie <i>b</i> . Jeżeli między zdarzeniami zachodzi taka relacja, oznacza to że jest ona prawdziwa dla wszystkich procesów.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Niech zdarzenie <i>a</i> poprzedza zdarzenie <i>b</i> <i>.</i> Relacja uprzedniości zdarzeń zachodzi w następujących przypadkach. Zdarzenia <i>a</i> i <i>b</i> działają wewnątrz tego samego procesu oraz <i>a</i> występuje przed <i>b</i> . W drugim przypadku <i>a</i> jest zdarzeniem wysłania komunikatu przez pewien proces, a <i>b</i> jest zdarzeniem odebrania tego komunikatu przez inny proces. Trzeci przypadek opisuje domknięcie przechodnie relacji uprzedniości. Mówimy, że zdarzenie <i>a</i> poprzedza zdarzenie <i>b</i> gdy istnieje sekwencja zdarzeń rozpoczynająca się od zdarzenia <i>a</i> i kończąca zdarzeniem <i>b</i> , taka że dla każdej pary kolejnych zdarzeń zachodzi jedna z dwóch wcześniej opisanych sytuacji.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Jeżeli między dwoma zdarzeniami nie zachodzi relacja uprzedniości, mówimy o nich, że są <b>współbieżne</b> (ang. <i>concurrent</i> ).<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Relacja uprzedniości zdarzeń jest relacją antysymetryczną oraz przechodnią, a tym samym jest relacją częściowego porządku.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Diagramy przestrzenno-czasowe</font></b><br>
            <hr size=2>
          </div>
          <br>
        </div>
        <div id=h.99 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2410gxc7fjdt_b.png" style=HEIGHT:343px;WIDTH:500px><br>
          <br>
          <b>Diagramy</b> <b>przestrzenno-czasowe</b> (ang<i>.</i> <i>space-time</i> <i>diagram</i> ) służą do graficznego zapisu realizacji przetwarzania rozproszonego. Osie diagramu reprezentują globalny upływ czasu, natomiast punkty na osiach oznaczają zdarzenia.<br>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Zegary logiczne</font></b><br>
          <hr size=2><br>
          <div id=u_yh style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2411c34tcvc6_b.png" style=HEIGHT:341px;WIDTH:500px><br>
            <br>
            Można wykazać, że synchronizacja zegarów nie musi być bezwzględna. W przypadku dwóch procesów, które się ze sobą nie komunikują w żaden sposób, nie ma potrzeby aby ich zegary były zsynchronizowane, ponieważ brak takiej synchronizacji będzie niezauważalny, a tym samym nie spowoduje żadnych problemów. Dla pewnej klasy algorytmów liczy się tylko spójność wewnętrzna zegarów, a niekoniecznie to że odzwierciedlają czas rzeczywisty. Dzieje się tak na przykład w wypadku kiedy istotna staję się kolejność występowania zdarzeń, a nie dokładny czas ich wystąpienia.<br>
            <br>
            <p>
              W dalszej części wykładu zostaną omówione algorytmy synchronizacji zegarów logicznych za pomocą znaczników czasu Lamporta i wektorowych znaczników czasu.
            </p>
            <br>
            <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd15 title=Sr-6-wyk-2.0-Slajd15> </a><br>
            <b style=COLOR:#3d85c6><font size=3>Znaczniki czasu Lamporta</font></b><br>
            <hr size=2>
          </div>
          <br>
        </div>
        <div id=z.31 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2412hkwfhxcr_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          Znaczniki czasu Lamporta zostały opracowane jako sposób pomiaru czasu logicznego. Każdemu zdarzeniu <i>a</i> przypisana jest pewna wartość czasu <i>C(a</i> <i>).</i> Jeżeli weźmiemy dwa zdarzenia <i>a</i> i <i>b</i> , przy czym <i>a</i> poprzedza zdarzenie <i>b</i> , to powinna zachodzić nierówność <i>C(a</i> <i>)&lt;</i> <i>C(b</i> <i>).<br>
          <br>
          </i>
          <p>
            W podejściu Lamporta wykorzystano bezpośrednio koncepcję relacji uprzedniości zdarzeń. Każdy wysłany komunikat zawiera czas swojego nadania. Odbiorca, który odbierze wiadomość porównuje czas jej nadania z własnym czasem. Jeśli zegar odbiorcy wskazuje czas mniejszy od czasu nadania komunikatu, przesuwa swój zegar w przód do wartości równej czasowi nadania powiększonej o pewną wartość <i>d</i> . Dodanie <i>d</i> wymusza postęp czasu pomiędzy każdą parą zdarzeń.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Rozszerzeniem tego algorytmu jest dodanie po przecinku do każdej wartości zegara np. numeru procesu. Robi się tak, gdyż w normalnych warunkach dwa zdarzenia mogłyby posiadać znaczniki czasowe o tej samej wartości. Dodatkowa informacja pozwala na rozróżnienie zdarzeń. Na przykład zdarzenie, które wystąpiło w procesie 4 w chwili gdy wartość jego zegara logicznego wynosiła 120, będzie oznaczone znacznikiem (120, 4).<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Zegar Lamporta spełnia kilka ważnych warunków. Jeżeli <i>a</i> poprzedza <i>b</i> , to <i>C(a</i> <i>)&lt;</i> <i>C(b</i> <i>).</i> Należy pamiętać, że implikacja taka nie zachodzi w odwrotną stronę. Algorytm Lamporta całkowicie porządkuje wszystkie zdarzenia w systemie.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Znaczniki Lamporta a relacja uprzedniości</font></b><br>
          <hr size=2>
        </div>
      </div>
    </div>
    <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd16 title=Sr-6-wyk-2.0-Slajd16> </a><br>
  </div>
  <div id=ya9j style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2414cj66n7dd_b.png" style=HEIGHT:344px;WIDTH:500px>
  </div>
  <br>
  Na ilustracji przedstawiono w prosty sposób zależności między relacją uprzedniości zdarzeń a znacznikami czasu Lamporta. Zauważmy, że znając znaczniki czasu Lamporta nie jesteśmy w stanie określić relacji uprzedniości między zdarzeniami. Natomiast w przypadku, gdy jedno zdarzenie poprzedza drugie, znajduje to również swoje odzwierciedlenie w wartościach znaczników czasu Lamporta.<br>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Wektorowe znaczniki czasu</font></b><br>
  <hr size=2><br>
  <div id=d-hw style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_241564nh2fft_b.png" style=HEIGHT:344px;WIDTH:500px><br>
    <br>
    <b>Wektorowe</b> <b>znaczniki</b> <b>czasu</b> (ang. <i>vector</i> <i>timestamps</i> ) są rozwinięciem koncepcji znaczników czasu Lamporta. Znaczniki czasu Lamporta pozwalają na całkowite uporządkowanie zdarzeń w systemie rozproszonym, ale na ich podstawie nie możemy stwierdzić jaki był związek między zdarzeniami. Na uchwycenie <b>przyczynowości</b> (ang. <i>casuality</i> ) pozwalają za to wektorowe znaczniki czasu.
    <p>
      <br>
    </p>
    <p>
      Każdy proces jest wyposażony w zegar <i>Vi</i> , który jest wektorem liczb całkowitych i ma długość <i>n</i> , równą liczbie procesów w systemie. Zegar taki może być rozpatrywany w kategoriach funkcji, która przypisuje pewien wektor <i>Vi(a</i> <i>)</i> każdemu zdarzeniu <i>a</i> . <i>Vi(a</i> <i>)</i> jest określane jako znacznik czasowy zdarzenia <i>a</i> w procesie <i>Pi</i> . Wartość <i>Vi[i</i> <i>]</i> (znana przez proces <i>Pi</i> ) jest równa liczbie zdarzeń jakie zaszły do tej pory w procesie <i>Pi</i> . <i>Vi[j</i> <i>]</i> dla <i>j</i> różnego od <i>i</i> jest wartością zegara procesu <i>Pj</i> , jaką zna proces <i>Pi</i> . Innymi słowy, w dowolnym momencie czasu, <i>j-ty</i> element <i>Vi</i> wskazuje czas pojawienia się ostatniego zdarzenia procesu <i>Pj</i> , które poprzedza (w sensie relacji uprzedniości zdarzeń) bieżący moment czasu w procesie <i>Pi</i> .<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Wartość zegara <i>Vi</i> jest zwiększana pomiędzy dowolnymi dwoma kolejnymi zdarzeniami w procesie <i>Pi</i> . Wektorowe znaczniki czasu przekazywane są razem z komunikatami. W ten sposób odbiorca jest powiadamiany o liczbie zdarzeń, które wystąpiły u nadawcy oraz u innych procesów, o których wiedział nadawca zanim wysłał komunikat. Po tym jak proces <i>Pi</i> otrzymuje od innego procesu <i>Pj</i> wektor <i>v</i> , aktualizuje własny ustawiając każdy wpis <i>Vi[k</i> <i>]</i> na wartość <i>maksimum{Vi[k</i> <i>],</i> <i>v[k</i> <i>]}.</i>
    </p>
    <p>
      <i><br>
      </i>
    </p>
    <p>
      Znaczniki wektorowe mają kilka istotnych cech. W każdym momencie czasu wartość <i>Vi[i</i> <i>]</i> jest niemniejsza niż wartość <i>Vj[i</i> <i>].</i> Ponadto jeżeli w systemie wykorzystującym zegary wektorowe zdarzenie <i>a</i> poprzedza przyczynowo zdarzenie <i>b</i> , to zachodzi własność <i>V(a</i> <i>)&lt;</i> <i>V(b</i> <i>).</i> Co ważniejsze implikacja ta jest również prawdziwa w odwrotnym wypadku, czyli jeżeli wartość znacznika wektorowego dla zdarzenia <i>a</i> jest większa od znacznika zdarzenia <i>b</i> , to prawdą jest to, iż <i>a</i> poprzedza <i>b</i> .
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Transakcje</font></b><br>
    <hr size=2><br>
  </div>
  <div id=did4 style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2416rb4n3qgc_b.png" style=HEIGHT:341px;WIDTH:500px><br>
    <br>
    Pojęcie <b>transakcji</b> (ang. <i>transaction</i> ) wprowadza pewne zasady dotyczące operacji na współdzielonych zasobach. Transakcja określa m.in. kolejność w jakiej wykonywane są operacje. Ważną cechą transakcji jest ochrona dzielonych zasobów przed jednoczesnym dostępem współbieżnych procesów. Dają one również możliwość wykonywania pewnych operacji w sposób niepodzielny, mimo że tak naprawdę może to być grupa wielu mniejszych operacji na różnych danych. Poza tym jeśli taka transakcja jest wycofywana z pewnych powodów, stan systemu może być przywrócony do momentu sprzed rozpoczęcia wykonywania transakcji.<br>
    <br>
    <p>
      Transakcje były wykorzystywane głównie do tej pory w systemach bazodanowych, jednakże coraz szerzej stosowane są w systemach operacyjnych, również tych rozproszonych.
    </p>
    <br>
    <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd19 title=Sr-6-wyk-2.0-Slajd19> </a><br>
    <b style=COLOR:#3d85c6><font size=3>Model transakcji</font></b><br>
    <hr size=2>
  </div>
  <br>
  <div id=bcfq style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2417f28qvdg7_b.png" style=HEIGHT:342px;WIDTH:500px>
  </div>
  <br>
  Mówiąc o transakcjach, często odnosimy się do transakcji występujących w biznesie. Nieprzypadkowa jest tu zbieżność nazw np. transakcje bankowe. Weźmy operację przelewu, która składa się z dwóch mniejszych operacji: pobranie pieniędzy z jednego konta i dodanie ich do drugiego konta. Nietrudno sobie wyobrazić, co by było gdyby jedna z tych operacji się nie powiodła (pojawienie się nadmiaru pieniędzy lub ich zniknięcie).<br>
  <br>
  <p>
    Podobne sytuacje występują również w systemach komputerowych. Załóżmy, że istnieje proces, który współpracując z innymi procesami wykonuje jakieś operacje. Po ukończeniu tych operacji chce je zatwierdzić i pyta w tym celu inne procesy, czy się zgadzają. Gdy jeden z procesów nie wyrazi zgody, wszystkie operacje i ich skutki muszą być cofnięte.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Systemy plików również, mogą wykorzystywać zalety transakcji do grupowania operacji na plikach. Z pewnością pozwala to na łatwiejsze utrzymanie spójności całego systemu.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Do sterowania transakcjami istnieje zestaw kilku podstawowych funkcji elementarnych. Zasięg transakcji wskazywany jest odpowiednio przez dwie funkcje: <i>początek_transakcji</i> oraz <i>koniec_transakcji</i>. W celu zatrzymania i wycofania transakcji możemy użyć funkcji <i>zaniechaj_transakcję</i> . Do nadzorowania operacji wewnątrz transakcji służą z kolei np. funkcje <i>czytaj</i> i <i>pisz</i> .
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Klasyfikacja transakcji</font></b><br>
  <hr size=2><br>
  <div id=ed26 style=TEXT-ALIGN:left>
    <div id=r970 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2419gmmj44dx_b.png" style=HEIGHT:342px;WIDTH:500px>
    </div>
    <br>
  </div>
  <p>
    Transakcje można podzielić na: transakcje płaskie (najprostsze), transakcje zagnieżdżone oraz transakcje rozproszone. Kolejne slajdy omawiają poszczególne typy transakcji.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Cechy transakcji płaskich</font></b><br>
  <hr size=2><br>
  <div id=jxw4 style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2420hrmgxccm_b.png" style=HEIGHT:343px;WIDTH:500px><br>
    <br>
    <b>Transakcje</b> <b>płaskie</b> (ang. <i>flat</i> <i>transactions</i> ), definiowane jako ciąg operacji, są najczęściej używaną klasą transakcji. Posiadają one jednak cechy, które uniemożliwiają wykonanie pewnych przydatnych w praktyce czynności. Przeszkodą okazuje się głównie niemożność zatwierdzenia lub wycofania wyników częściowych.<br>
    <br>
    <p>
      Rozpatrzmy transakcję zakupu pewnej liczby książek za pomocą serwisu internetowego. Po wybraniu kilku interesujących nas książek składamy zamówienie (rozpoczynamy transakcję). Okazuje się jednak, że w rzeczywistości oferowane przez serwis internetowy książki znajdują się w odległych od siebie geograficznie magazynach. W tym momencie do każdego z magazynów musi spłynąć odpowiednie zamówienie na dostępne tam książki. W jakimś momencie transakcji może się okazać, że nie ma jednej z książek. Pojawia się pytanie co zrobić jeżeli niektóre magazyny przetworzyły już część globalnego zamówienia. Czy dać użytkownikowi możliwość zamówienia części książek? Jeżeli wszystkie zamówienia musiałyby być cofnięte, zostałby zmarnowany pewien być może niemały nakład pracy, a tymczasem użytkownik mimo braku książki chce kupić pozostałe. Jak łatwo zauważyć częściowe zatwierdzanie transakcji w tym wypadku byłby bardzo przydatne.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Drugą kwestią, jaka się pojawia w tym przykładzie, jest czas przetwarzania zamówień, który może się znacznie różnić w zależności od magazynu. Żeby nie tracić czasu, można by wysłać część książek do klienta wcześniej.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Transakcje zagnieżdżone</font></b><br>
    <hr size=2><br>
    <div id=x6kw style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2421fsrbtgdt_b.png" style=HEIGHT:340px;WIDTH:500px><br>
      <br>
      Niektórych problemów, które pojawiają się przy wykorzystywaniu transakcji płaskich, można się pozbyć korzystając z <b>transakcji</b> <b>zagnieżdżonych</b> (ang. <i>nested</i> <i>transaction</i> ).<br>
      <br>
      <p>
        Transakcja zagnieżdżona jest złożona z pewnej liczby <b>podtransakcji</b> (ang. <i>subtransaction</i> ). Każda transakcja w ramach transakcji zagnieżdżonej może również zawierać swoje podtransakcje itd. Podtransakcje mogą być wykonywane na różnych maszynach, jeżeli pozwoli to np. na zwiększenie efektywność przetwarzania.
      </p>
      <p>
        <br>
      </p>
      <p>
        Użycie podtransakcji implikuje pewien problem w postaci braku ich trwałości. Weźmy transakcja zagnieżdżoną, która składa się z pewnej liczby zatwierdzonych podtransakcji. Jeżeli taka transakcja zostanie teraz wycofana, jej skutki muszą być usunięte. Tym samym do wycofania zmuszone są zatwierdzone wcześniej podtransakcje.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        W chwili rozpoczęcia, podtransakcja dysponuje stanem zasobów, jakie udostępniła jej transakcja nadrzędna. Kiedy podtransakcja zostaje zatwierdzona, wyniki jej działania stają się widoczne dla jej transakcji nadrzędnej, a tym samym dla wszystkich następujących po niej podtransakcji.
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Transakcje rozproszone</font></b><br>
      <hr size=2><br>
    </div>
    <div id=en:0 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2422fm5g6kwn_b.png" style=HEIGHT:341px;WIDTH:500px><br>
      <br>
      <br>
    </div>
    Analizowalizując ograniczenia transakcji płaskich na przykładzie transakcji zakupu książek z różnych, geograficznie rozproszonych magazynów, naturalnym stało się wykorzystanie transakcji zagnieżdżonych. Za pomocą transakcji zagnieżdżonych mogliśmy podzielić jedną transakcję zakupu książek na kilka mniejszych podtransakcji, działających w ramach poszczególnych magazynów. Każda z takich podtransakcji mogła działać i być zrealizowana niezależnie od innych podtransakcji.<br>
    <br>
    <p>
      W powyższym przykładzie pojawił się jednak jeszcze jeden istotny element, którego nie analizowaliśmy: rozproszenie całego systemu. Transakcje zagnieżdżone nie stanowią od razu o tym, że dana transakcja działa w środowisku rozproszonym. Stanowi ona jedynie pewien sposób organizacji pracy systemu. W celu wyróżnienia transakcji, które działają na różnych maszynach, wprowadzono pojęcie <b>transakcji</b> <b>rozproszonych</b> (ang. <i>distributed</i> <i>transactions</i>).<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Zdarzają się sytuacje, w których jedna transakcja musi mieć dostęp do danych w kilku miejscach jednocześnie. Mamy wtedy oczywiście do czynienia z transakcją rozproszoną, ale niekoniecznie zagnieżdżoną. Dla uwypuklenia głównej różnicy: transakcje zagnieżdżone stosuje się ze względu na logikę ich pracy, natomiast transakcje rozproszone ze względu na rozproszenie danych, na których operują.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Prywatna przestrzeń robocza</font></b><br>
    <hr size=2>
  </div>
  <br>
  <div id=n4wf style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_24232nqwr8cf_b.png" style=HEIGHT:341px;WIDTH:500px><br>
    <br>
    Transakcje są bardzo wygodnym sposobem organizowania pracy. Jednak, aby móc się o tym przekonać w praktyce, należy najpierw je jakoś zaimplementować. Do tego celu służą m.in. dwie metody. Jedną z nich zaprezentujemy poniżej, a drugą trochę później w dalszej części wykładu.<br>
    <br>
    <p>
      Pierwsze podejście polega na przypisaniu każdej transakcji, w momencie kiedy jest uruchamiana, prywatnej przestrzeni roboczej. W przestrzeni tej znajdują się wszystkie dane, do których transakcja ma dostęp. W trakcie działania transakcja operuje tylko na swojej prywatnej przestrzeni, a nie bezpośrednio na oryginalnych danych.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Istnieje kilka sposobów realizacji takiego pomysłu. Najprostszy z nich zakłada skopiowanie całości oryginalnych danych do przestrzeni roboczej transakcji. Ze względu na koszt kopiowania nie będziemy się dalej zajmować tą realizacją i przejdziemy do następnej zmodyfikowanej wersji. Przy realizacji drugiego sposobu wykorzystano spostrzeżenie, iż nie ma potrzeby tworzenia kopii danych, które są tylko odczytywane przez transakcję. Można tu wykorzystać oryginalne dane. Kolejna realizacja podejmuje problem zapisu. W tym celu transakcja kopiuje do swojej przestrzeni roboczej tylko tablicę odnośników do bloków potrzebnych plików z danymi. Podczas odczytu odczytywane są po prostu oryginalne dane, natomiast przy zapisie tworzona jest kopia modyfikowanego bloku (tzw. cienie bloków – ang. <i>shadow</i> <i>blocks</i> ) i dopiero do niego zapisywane są nowe dane. Po zatwierdzeniu takiej transakcji odnośniki do zmodyfikowanych bloków zastępują oryginalne bloki.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Ilustracja na slajdzie prezentuje przykład realizacji transakcji w systemie plików. Na potrzeby transakcji zapamiętywane są w jej przestrzeni roboczej indeksy bloków pliku, na których działa. Gdy transakcja modyfikuje blok 1, zostaje on skopiowany i powstaje cień bloku, 1’. Dodatkowo transakcja dodała nowy blok, do którego indeks pamiętany jest w prywatnej przestrzeni adresowej do czasu zatwierdzenia transakcji.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Rejestrowanie z wyprzedzeniem</font></b><br>
    <hr size=2><br>
    <div id=ys59 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2424cj3k8kg2_b.png" style=HEIGHT:340px;WIDTH:500px><br>
      <br>
      <b>Rejestrowanie</b> <b>z</b> <b>wyprzedzeniem</b> (ang. <i>writeahead</i> <i>log</i> ) jest metodą realizacji transakcji, która pozwala na modyfikowanie oryginalnych plików, z których korzysta transakcja. Zanim jednak następuje sama operacja zapisu, fakt ten odnotowywany jest w specjalnym rejestrze w postaci rekordu z informacjami o transakcji, modyfikowanym przez nią pliku i bloku oraz nową i starą wartością bloku.<br>
      <br>
      <p>
        W momencie gdy transakcja zostaje zatwierdzona, do wspomnianego rejestru wpisywany jest tylko fakt samego zatwierdzania, gdyż dane zostały już wcześniej zaktualizowane. Kiedy jednak transakcja zostaje anulowana, przydatny okazuje się rejestr, który służy do przywrócenia stanu sprzed transakcji. Operacja przywracania polega w skrócie na odczytaniu od końca rekordów rejestru i wycofaniu (ang. <i>rollback</i> ) zapisanych w nim zmian.
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Sterowanie współbieżnością</font></b><br>
      <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd27 title=Sr-6-wyk-2.0-Slajd27> </a><br>
      <div id=fz98 style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2425f7h4n3fz_b.png" style=HEIGHT:340px;WIDTH:500px><br>
        <br>
        W celu zachowania spójnych danych, na których operują współbieżne procesy potrzebna jest specjalna kontrola. Za taką kontrolę odpowiedzialne jest sterowanie współbieżnością. Sterowanie to polega m.in. na udostępnianiu transakcjom odpowiednich danych w odpowiedniej kolejności. Wynik transakcji powinien być taki sam, jakby transakcje były uruchamiane szeregowo według pewnego porządku.<br>
        <br>
        <p>
          W celu lepszego zrozumienia metod sterowania współbieżnością, można wyróżnić w nim trzy elementy składowe w postaci <b>zarządcy</b> <b>danych</b> (ang. <i>data</i> <i>manager</i> ), <b>planisty</b> (ang. <i>scheduler</i> ) oraz <b>zarządcy</b> <b>transakcji</b> (ang. <i>transaction</i> <i>manager</i> ). Zarządca danych znajduje się na najniższym poziomie i zajmuje się rzeczywistymi operacjami odczytu i zapisu. Wyżej znajduje się planista, który odpowiada za właściwą politykę sterowania współbieżnością. Określa on kolejność operacji wykonywanych przez poszczególne transakcje. Zapewni również spójność i izolację transakcji. Zarządca transakcji odpowiada głównie za zapewnienie niepodzielności transakcji i wysyłanie zleceń do planisty.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Sterowanie współbieżnością - problemy</font></b><br>
        <hr size=2>
      </div>
      <br>
    </div>
    <div id=gan0 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2426ckgr3jg7_b.png" style=HEIGHT:341px;WIDTH:500px><br>
      <br>
      Sterowanie współbieżnością transakcji napotyka na dwa zasadnicze problemy: problem <i>utraconej</i> <i>aktualizacji</i> oraz problem <i>niespójnych</i> <i>odzyskań</i> .<br>
      <br>
      <p>
        Zilustrujmy teraz problem utraconej aktualizacji na przykładzie dwóch współbieżnych transakcji, dokonujących operacji na wspólnej danej. Przypuśćmy, że istnieje pewna dana <i>x</i> równa 5, do której transakcja <i>T1</i> chce dodać wartość 3, a transakcja <i>T2</i> chce dodać wartość 2. Załóżmy, że scenariusz wykonania obu transakcji wygląda następująco: transakcja <i>T1</i> odczytuje wartość <i>x</i> , chwilę później wartość <i>x</i> odczytuje transakcja <i>T2</i> , transakcja <i>T1</i> dodaje do <i>x</i> wartość 3, transakcja <i>T2</i> dodaje do <i>x</i> 2. Ostatecznie wszystkie te operacje sprawiły, że <i>x</i> jest równy 7, mimo że powinien wynieść 10. Stało się tak dlatego, iż wartości <i>x</i> jaką modyfikowała transakcja <i>T2</i> była nieaktualna w momencie zapisu. Innymi słowy transakcja <i>T2</i> polegała na odczycie, który był nieaktualny.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Prześledźmy drugi przykład, w którym występuje z kolei problem niespójnych odzyskań. Znowu załóżmy, że mamy dwie współbieżne transakcje <i>T1</i> i <i>T2</i> , które operują na zmiennych <i>x</i> i <i>y</i> , które początkowo przyjmują odpowiednio wartości 5 i 4. Transakcja <i>T1</i> odejmuje wartość 2 od <i>x</i> , a następnie dodaje ją do <i>y</i> . Transakcja <i>T2</i> ma za zadanie zsumowanie wartości <i>x</i> <i>i</i> <i>y</i> . Scenariusz wykonania transakcji niech wygląda następująco: transakcja <i>T1</i> odczytuje wartość <i>x</i> , transakcja <i>T1</i> zmniejsza odczytaną wartość <i>x</i> o 2, transakcja <i>T2</i> odczytuje wartość <i>x</i> , transakcja <i>T2</i> odczytuje wartość <i>y</i> i sumuje z wcześniej odczytaną wartością, transakcja <i>T1</i> odczytuje wartość <i>y</i> i dodaje do niej wartość 2. Suma uzyskana przez transakcję <i>T2</i> wyniosła ostatecznie 7, a powinna oczywiście 9. Błąd, który został tu popełniony, to zsumowanie przez transakcję <i>T2</i> wartości <i>x</i> i <i>y</i> , podczas gdy transakcja <i>T1</i> wykonała się tylko częściowo.
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Szeregowalność</font></b><br>
      <hr size=2><br>
      <div id=q-bz style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2427hnbzshc7_b.png" style=HEIGHT:341px;WIDTH:500px><br>
        <br>
        Antidotum na niektóre problemy związane ze sterowaniem współbieżnością jest tzw. <b>szeregowalność</b> (ang. <i>serializability</i> ). Szeregowalność pozwala na zachowanie izolacji transakcji. Sprawia, że wynik kilku współbieżnych transakcji, jest identyczny z wynikiem, który uzyskalibyśmy gdyby te transakcje uszeregować w pewien sposób jedna po drugiej.<br>
        <br>
        <p>
          W ogólności transakcję można przedstawić jako ciąg operacji czytania i zapisywania danych. Sterowanie współbieżnością polega na właściwej obsłudze operacji konfliktowych, czyli takich które działają na wspólnych danych, z czego co najmniej jedna jest operacją zapisu.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          W przypadku algorytmów sterowania współbieżnością istnieją dwie główne metody używane do synchronizacji zapisów i odczytów. Pierwsza z nich to metoda wzajemnego wykluczania przy dostępie do wspólnych danych. Druga to użycie znaczników czasowych do porządkowania operacji.<br>
        </p>
        <p>
          <br>
        </p>
        <p>
          Oprócz tego rozróżnia się pesymistyczne i optymistyczne sterowanie współbieżnością. W przypadku metod pesymistycznych konflikty są usuwane zanim do nich dojdzie. Metody optymistyczne zakładają natomiast, że konflikty raczej nie wystąpią i odkładają synchronizacje na koniec, co grozi zaniechaniem transakcji.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Szeregowalność - przykład</font></b><br>
        <hr size=2><br>
        <div id=dywt style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2428dvw56kgs_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Aby współbieżne transakcje mogły być wykonane prawidłowo ich plan wykonania (uporządkowanie operacji) musi uwzględniać szeregowalność. Jeżeli plan nie jest szeregowy, mówimy o nim, że jest planem niedopuszczalnym, a jego wykonanie daje błędne wyniki transakcji. W przeciwnym wypadku mamy do czynienia z planem dopuszczalnym, który tworzy wyniki zgodne z szeregowym wykonaniem transakcji.<br>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Blokowanie dwufazowe</font></b><br>
          <hr size=2><br>
          <div id=s6m4 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2429f4br9vf5_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            <b>Algorytm</b> <b>blokowania</b> <b>dwufazowego</b> (ang. <i>two-phase</i> <i>locking</i> <i>–</i> <i>2PL</i> ) jest jedną z najpopularniejszych metod implementacji transakcji. Algorytm ten należy do ogólniejszej klasy algorytmów sterowania współbieżnością, które stosują blokowanie. Działanie takich algorytmów w najprostszym przypadku polega na założeniu blokady na danej, która ma być zapisana lub odczytana, a po wykonaniu operacji blokada jest zwalniana.
            <p>
              <br>
            </p>
            <p>
              Algorytm blokowania dwufazowego składa się z dwóch faz: <b>fazy</b> <b>wzrostu</b> (ang. <i>growing</i> <i>phase</i> ) oraz <b>fazy</b> <b>zmniejszania</b> (ang. <i>shrinking</i> <i>phase</i> ). W pierwszej fazie transakcja może blokować zasoby, ale nie wolno jej zwalniać zasobów, które wcześniej już zablokowała. W drugiej fazie transakcja może zwalniać zasoby, lecz nie wolno jej blokować żadnych nowych zasobów. Jeżeli proces nie chce modyfikować danych dopóki nie osiągnie momentu przed fazą zmniejszania, to w razie niepowodzenia przy zakładaniu jakiejś blokady może on zwolnić wszystkie blokady i rozpocząć ponownie algorytm.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Kluczową własnością tego algorytmu jest fakt, że jeżeli wszystkie transakcje działają według schematu blokowania dwufazowego, to ich scenariusze utworzone na skutek przeplotu są uszeregowalne.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Istnieje kilka odmian tego algorytmu. Np. <b>ścisłe</b> <b>blokowanie</b> <b>dwufazowe</b> (ang. <i>strict</i> <i>two-phase</i> <i>locking</i> ) jest realizowane w systemach, gdzie faza zmniejszania nie występuje dopóki transakcja nie zostanie zakończona. Atutem takiego rozwiązania jest to, że transakcja zawsze czyta wartości zapisane tylko przez zatwierdzone transakcje. Ponadto operacjami blokowania i zwalniania może zająć się system, żeby nie angażować w tym celu transakcji.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Należy zwrócić uwagę na jeden istotny fakt, że algorytm blokowania dwufazowego nie uwalnia nas od problemu zakleszczenia, w wypadku gdy dwie transakcje ubiegają się o te same zasoby tylko w odwrotnej kolejności. Można tutaj wykorzystać pewien z góry ustalony porządek przydzielania zasobów. Inna metodą jest tworzenie i przechowywanie grafu procesów, które posiadają blokady. Jeszcze inne podejście bazuje, na znanym maksymalnym czasie przez jaki może być założona blokada, tak że po wykryciu blokady przez inny proces może on stwierdzić po pewnym czasie, że wystąpiło zakleszczenie.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Ilustracja blokowania dwufazowego</font></b><br>
            <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd32 title=Sr-6-wyk-2.0-Slajd32> </a><br>
          </div>
          <div id=zttm style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2430czb5crz5_b.png" style=HEIGHT:341px;WIDTH:500px><br>
            <br>
            Na wykresie przedstawiono etapy działania algorytmu blokowania dwufazowego. Można zauważyć, że wraz z upływem czasu rośnie liczba założonych blokad. Gdy zostaną założone wszystkie blokady, następuje tzw. punkt blokady i może rozpocząć się przetwarzanie odpowiednich danych. Po zakończeniu operacji blokady są zwalniane, co ilustruje faza zmniejszania na wykresie.<br>
            <br>
          </div>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Pesymistyczne porządkowanie według znaczników czasu</font></b><br>
          <hr size=2>
        </div>
        <br>
        <div id=idez style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2431gd2cwxgw_b.png" style=HEIGHT:344px;WIDTH:500px>
        </div>
        <br>
      </div>
    </div>
    Kolejny algorytm to <b>pesymistyczne</b> <b>porządkowanie</b> <b>według</b> <b>znaczników</b> <b>czasu</b> (ang. <i>pessimistic</i> <i>timestamp</i> <i>ordering</i> ). W algorytmie pesymistycznego sterowania współbieżnością każda transakcja <i>T</i> jest opisywana znacznikiem czasowym <i>t(T</i> <i>).</i> Ponadto każda zmienna <i>x</i> również opatrywana jest dwoma znacznikami czasowymi: znacznikiem czasu zapisu <i>tz(x</i> <i>)</i> oraz znacznikiem czasu odczytu <i>tc(x</i> <i>).</i> Wartość <i>tz(x</i> <i>)</i> jest równa znacznikowi transakcji, która jako ostatnio pisała do zmiennej <i>x</i> , analogicznie jest z wartością <i>tc(x</i> <i>),</i> z tym że operacja dotyczy oczywiście odczytu. Algorytm wymaga, aby znaczniki czasu były unikalne. W tym celu można zastosować np. algorytm Lamporta.<br>
    <br>
    <p>
      W wypadku wystąpienia konfliktu między operacjami, w pierwszej kolejności obsługiwana jest ta, która ma mniejszy znacznik czasowy.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Zobaczmy teraz co się dzieje w przypadku, kiedy planista otrzyma od transakcji <i>T</i> zlecenie na operację odczytu lub zapisu zmiennej <i>x</i> <i>.</i> Jeżeli transakcja zleca odczyt, planista porównuje wartości znacznika <i>t</i> transakcji z wartością <i>tz(x</i> <i>).</i> Jeżeli wystąpił zapis na zmiennej <i>x</i> w momencie, kiedy transakcja <i>T</i> była już wykonywana, czyli gdy <i>t</i> <i>&lt;</i> <i>tz(x</i> <i>),</i> <i>T</i> musi zostać zaniechana. W przeciwnym wypadku <i>T</i> wykonuje operację, a wartość <i>tc(x</i> <i>)</i> zostaje ustawiona na <i>max[t</i> <i>,</i> <i>tc(x</i> <i>)].</i>
    </p>
    <p>
      <i><br>
      </i>
    </p>
    <p>
      Podobna sytuacja występuje dla operacji zapisu. Po nadejściu zlecenia zapisu, porównujemy wartości <i>t</i> oraz <i>tc(x</i> <i>).</i> Jeśli <i>t</i> <i>&lt;</i> <i>tc(x</i> <i>),</i> transakcja zostaje zaniechana, gdyż zmienna <i>x</i> została w tym przypadku odczytana po rozpoczęciu transakcji <i>T</i> . Gdy zachodzi natomiast sytuacja odwrotna operacja może być wykonana, a wartość <i>tz(x</i> <i>)</i> odpowiednio ustawiona na <i>max[t</i> <i>,</i> <i>tz(x</i> <i>)].</i>
    </p>
    <p>
      <i><br>
      </i>
    </p>
    <p>
      Porównując ten algorytm do algorytmu blokowania dwufazowego, można zauważyć, że przeploty operacji, które są akceptowalne dla jednego algorytmu, niekoniecznie są akceptowalne dla drugiego i odwrotnie.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Zaletą tego algorytmu jest to, że uwalnia nas od problemu zakleszczania.
    </p>
    <br>
    <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd34 title=Sr-6-wyk-2.0-Slajd34> </a><br>
    <b style=COLOR:#3d85c6><font size=3>Porządkowanie pesymistyczne - przykłady</font></b><br>
    <hr size=2><br>
  </div>
  <div id=gqyh style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2432hg93brdj_b.png" style=HEIGHT:344px;WIDTH:500px>
  </div>
  <br>
  W prezentowanych przykładach zakładamy istnienie trzech transakcji <i>T0</i> , <i>T1</i> oraz <i>T2</i> . Dodatkowo zakładamy, że transakcja <i>T0</i> wykonywała się jako pierwsza przed rozpoczęciem pozostałych transakcji i korzystała z wszystkich danych, na których operują transakcje <i>T1</i> oraz <i>T2</i> . Oznacza to, że operacje zapisu i odczytu dla zmiennych są oznaczone na początku znacznikiem czasu transakcji <i>T0</i> . Ponadto niech <i>t(T1</i> <i>)</i> <i>&lt;</i> <i>t(T2</i> <i>),</i> czyli transakcja <i>T1</i> rozpoczęła się przed transakcją <i>T2</i>.<br>
  <br>
  <p>
    Na początku rozpatrzmy odczyt zmiennej <i>x</i> przez transakcję <i>T1</i> dla scenariusza przedstawionego w przykładzie 1. Transakcja <i>T0</i> , która działała od dłuższego czasu wykonała zapis. Po tej operacji zapisu widzimy, że rozpoczęła się transakcja <i>T1</i> i na tym kończy się sekwencja operacji. Nie występuje dalej żadna operacja zapisu na zmiennej <i>x</i> , która mogłaby powodować konflikt z operacją odczytu <i>x</i> . W związku z tym odczyt zmiennej <i>x</i> może być wykonany bezkonfliktowo.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Zajmijmy się teraz przykładem 2., gdzie transakcja <i>T1</i> żąda zapisu zmiennej <i>x</i> . Są tu dwie kolejne operacje zapisu i odczytu <i>x</i> wykonane przez transakcję <i>T0</i> . Po nich rozpoczyna się transakcja <i>T1</i> , która chce następnie pisać do zmiennej <i>x</i> . Ponieważ transakcja <i>T1</i> nie została jeszcze zatwierdzona, zapis wykonywany jest tymczasowo do momentu zatwierdzenia transakcji.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    W ostatnim wypadku transakcja <i>T1</i> również żąda zapisu <i>x</i> , ale w trakcie jej trwania, a przed żądanym przez nią zapisem, wystąpił zapis wykonany przez inną transakcję <i>T2</i> . Transakcja <i>T1</i> musi zostać zaniechana.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Optymistyczne porządkowanie według znaczników czasu</font></b><br>
  <hr size=2><br>
  <div id=god: style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2433c8cqrshb_b.png" style=HEIGHT:344px;WIDTH:500px><br>
    <br>
    Ostatni algorytm to <b>optymistyczne</b> <b>porządkowanie</b> <b>według</b> <b>znaczników</b> <b>czasu</b> (ang. <i>optimistic</i> <i>timestamp</i> <i>ordering</i> ). Optymistyczne sterowanie współbieżnością transakcji jest kolejnym podejściem do jednoczesnego wykonywania kilku transakcji. Ogólna idea polega na tym, że transakcja jest wykonywana nawet w przypadku, kiedy występują konflikty. Ich rozwiązanie jest odkładane do czasu ewentualnego zatwierdzania. Jeżeli okaże się, że jakaś inna transakcja <i>T1</i> zmieniła dane od czasu rozpoczęcia naszej transakcji <i>T2</i> , to <i>T2</i> zostaje zaniechana. W przeciwnym razie <i>T2</i> zostaje zatwierdzona.<br>
    <br>
    <p>
      Zwróćmy uwagę, że wraz z zastosowaniem takiego podejścia do sterowania współbieżnością, można wykorzystać w transakcjach prywatną przestrzeń roboczą. W ten sposób każda transakcja może działać lokalnie bez przejmowania się innymi transakcjami.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Inną ważną cechą optymistycznego algorytmu jest brak zakleszczeń, gdyż transakcje w trakcie działania nie zajmują się konfliktami i działają dalej.
    </p>
    <br>
    <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-6-wyk-2.0-Slajd36 title=Sr-6-wyk-2.0-Slajd36> </a>
  </div>
</div>
<br></body>
</html>